剑指Offer 36 数组中的逆序对（归并）

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

思路

其实思路也很简单，只要你知道归并排序是怎么做到的；简单来说，归并排序分为两步，划分，和归并；难点就在归并上，简单地说，归并时已经比较的在都在一9起，然后我们取两个来比较一下呗；
（5，7）与（4，6）正常归并肯定是从第一个开始，我们不要，我们从后往前来，比如说7>6 那么7也一定大于6之前的数；这样比较就很简单了；

代码

代码有两种形式，第一种就是正常归并，但是你递归一次，原数组肯定要发生变化的啊；另外一种呢：不需要每次赋值，直接将我们创造的数组与原数组调换即可；

static public int InversePairs(int [] array) {
    if(array==null||array.length==0)
    {
        return 0;
    }
    int [] result = new int[array.length];
    int a= Merge(array, result, 0, array.length - 1)%1000000007;
    System.out.println(Arrays.toString(result));
    return a;
 }
 public static  int Merge(int [] arr,int [] result,int start , int end)
 {
     if (start==end)                    //递归结束
     {
         result[start]= arr[start];
         return 0;
     }
     int mid = (end+start)>>1;
     int left = Merge(arr,result,start,mid)%1000000007;
     int right = Merge(arr,result,mid+1,end)%1000000007;
     /*
     左结束，右结束
     结果数组的下标index;
     逆序数 count
      */
     int leftend = mid;
     int rightend = end;
     int index = end;
     int count = 0;
     while (leftend>=start&&rightend>mid)
     {
         if (arr[leftend]>arr[rightend])
         {
             result[index--]=arr[leftend--];
             count+= rightend-mid;
             if(count>=1000000007)//数值过大求余
             {
                 count%=1000000007;
             }
         }
         else
             result[index--]=arr[rightend--];
     }
     for (;leftend>=start; leftend--)                //复制剩余的左边
     {
         result[index--]=arr[leftend];
     }
     for (;rightend>mid; rightend--)                 //复制右面的剩余
     {
         result[index--] = arr[rightend];
     }
     for (int i = start;i<=end;i++)                  //改变原数组
     {
         arr[i]=result[i];
     }
     return  (count+left+right)%1000000007;
 }

   static public int InversePairs(int [] array) {
        int [] result = new int[array.length];
       for (int i = 0; i < array.length; i++) {
           result[i] = array[i];
       }
        int a= Merge(array, result, 0, array.length - 1)%1000000007;
       System.out.println(Arrays.toString(result));
       return a;
    }
   static public   int Merge(int [] arr,int [] result,int start , int end)
    {
        if (start==end)
        {
            result[start]= arr[start];
            return 0;
        }
        int lengh = (end-start)>>1;
        int mid = start + lengh;
        int left = Merge(result,arr,start,mid)%1000000007;
        int right = Merge(result,arr,mid+1,end)%1000000007;
        
        int leftend = mid;
        int rightend = end;
        int index = end;
        int count = 0;
        while (leftend>=start&&rightend>mid)
        {
            if (arr[leftend]>arr[rightend])
            {
                result[index--]=arr[leftend--];
                count+= rightend-mid;
                if(count>=1000000007)//数值过大求余
                {
                    count%=1000000007;
                }
            }
            else
                result[index--]=arr[rightend--];
        }
        for (;leftend>=start ; --leftend)
        {
            result[index--]=arr[leftend];
        }
        for (;rightend>=mid+1;--rightend)
        {
            result[index--] = arr[rightend];
        }
        //不需要改变原数组
//        for (int i = start; i <=end;i++)
//        {
//            arr[i]=result[i];
//        }
        return  (count+left+right)%1000000007;
    }

收获

就是坑在引用上了啊！！！
人家是这么写的

int[] copy = new int[array.length];        
for(int i=0;i<array.length;i++)       
{ 
 copy[i] = array[i];        
}

我是这么写的：

1	int [] copy = array; //这是引用啊啊啊啊啊啊啊啊；

所以就找了好长时间的错误

2017-04-01